package mht.practice.sort;

/**
 * 插入排序法
 * Created by MHT on 2017/8/25.
 */
public class InsertionSort {

    // 我们的算法类不允许产生任何实例
    private InsertionSort(){}

    //数组中两个元素进行位置交换
    private static void swap(Object arr[],int i,int j){
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 对arr[l...r]的区间使用InsertionSort排序
    public static void sort(Comparable arr[],int l,int r){

        assert l >= 0 && l <= r && r < arr.length;

        for( int i = l + 1 ; i <= r ; i ++ ){
            Comparable e = arr[i];
            int j = i;
            for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

    // 对整个arr数组使用InsertionSort排序
    public static void sort(Comparable arr[]){

        int n = arr.length;
        for (int i=0;i<n;i++){
            // 寻找元素arr[i]合适的插入位置
            for (int j=i;j>0;j--){
                if (arr[j].compareTo(arr[j-1]) < 0){
                    swap(arr,j,j-1);
                }
                else
                    break;
            }
        }
    }

    public static void main(String[] args) {

//        //基本数组测试
//        Comparable[] a = {1234,912,844,753,623,510,455,326,210,110};
//        InsertionSort.sort(a);
//        for (int i=0;i<a.length;i++){
//            System.out.print(a[i]+"  ");
//        }
//        System.out.println();

        int N = 20000;
        Integer[] b = SortTestHelper.generateRandomArray(N,0,100000);
        SortTestHelper.testSort("mht.practice.sort.InsertionSort",b);
    }


}
